Teorema de Popoviciu

El teorema de Popoviciu es un resultado en matemáticas, establecido por Tiberius Popoviciu, sobre el número de formas en que se puede expresar una cantidad como suma de múltiplos de otras dos cantidades y está relacionado con el problema de las monedas de Frobenius y establece:

Si a y b son dos números enteros primos relativos, entonces el número de formas de expresar un entero positivo n como combinación lineal no negativa de a y b es ${\frac {n}{ab}}-\left\{{\frac {rn}{a}}\right\}-\left\{{\frac {sn}{b}}\right\}+1$ donde r y s son dos números enteros positivos que satisfagan las relaciones de congruencia $bs\equiv 1{\pmod {a}},\quad ar\equiv 1{\pmod {b}}$ y las llaves $\{x\}$ representan la función parte fraccional: $\{x\}=x-\lfloor x\rfloor$.

Otra forma de interpretar la fórmula anterior, es como el número de formas en que se puede dividir el entero n como suma no ordenada en donde los sumandos son únicamente a y b. En otras palabras, da el número de particiones restringidas de n en el conjunto {a, b}.

Ejemplo

En el contexto del problema de las monedas de Frobenius, se desea encontrar el número de formas de reunir $20 usando únicamente monedas de $3 y $4. Como ejemplos: {$4, $4, $3, $3, $3, $3} o {$4, $4, $4, $4, $4} y podría haber otras.

Cada una de ellas corresponde a una combinación lineal positiva en donde los coeficientes son el número de veces que se usa cada denominación. En el ejemplo, las combinaciones lineales son 2·4 + 4·3 y 5·4 + 0·3.

Aplicando la fórmula de Popoviciu, sustituimos n=20, a=3, b=4. Los números r y s deben satisfacer las ecuaciones

$3r\equiv 1{\pmod {4}},\qquad 4s\equiv 1{\pmod {3}}$

Una posible solución es r=3 y s=1, ya que $3\cdot 3=9\equiv 1{\pmod {4}}\quad ,$ y $1\cdot 4=4\equiv 1{\pmod {3}}$.

Los términos que aparecen en el teorema de Popoviciu son:

${\frac {n}{ab}}={\frac {20}{3\times 4}}={\frac {20}{12}}={\frac {5}{3}},$

$-\left\{{\frac {rn}{a}}\right\}=-\left\{{\frac {3\cdot 20}{4}}\right\}=-\left\{15\right\}=0$

$-\left\{{\frac {sn}{b}}\right\}=-\left\{{\frac {1\cdot 20}{3}}\right\}=-{\frac {2}{3}}$

Entonces el teorema de Popoviciu establece que el número

${\frac {n}{ab}}-\left\{{\frac {rn}{a}}\right\}-\left\{{\frac {sn}{b}}\right\}+1={\frac {5}{3}}-{\frac {2}{3}}+1=2$

es el número total de formas de expresar 20 como combinación lineal no negativa de 3 y 4, por lo que se concluye que las dos mostradas inicialmente son las únicas posibles.

Bibliografía

• Matthias Beck; Sinai Robins (2007). Computing the Continuous Discretely. Springer. ISBN 9780387291390. 

• Datos: Q6141872